python iterator和generator雜談之二

囉唆一下：在今天的文章中會提到一些二元樹的相關知識，還不懂的讀者們可以參考以下資源： http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html

昨天用了年輕不懂事的技術文解釋了iterator擋了一天鐵人賽，今天要開始講解究竟何為generator。

其實generator也是一種特別的iterator，你一樣可以用__next__不停的讓他吐出東西，也就是我們所說的迭代行為，但不同的是，一般的iterator都會定義__next__這個內部函數，因為iterator的一個最基礎要件就是你呼叫他的_next_他就要返回一個東西給你，而generator呢，他握有一個特別的權柄，就是yield這個語句，因為有了yield，讓generator有了很多一般iterator所沒有的好處：
(1) 不需要定義__next，精簡的代碼使得代碼可讀性提高
(2) 大大減少了記憶體的使用率
(3) 可以用'yield from'輕鬆實作一個遞迴式的迭代行為
(4) 可以建立一個可拆式的資料管線，減少了不同工作階段的耦合性

這些好處讓generator在一般iterator中顯得鶴立雞群，也讓我覺得generator是python裡最優美且實用的一個特性(加個"之一"好了，另外一個我最喜歡的特性就是
"x,y = y,x"，懶人式swap XD)，上述的一些優點或許讓你看的似懂非懂，沒關係，以下會用實際的例子試著讓大家了解，先來一個簡單的生成器範例：

In python3 shell:
>>> def my_range(n):
...     i = 0
...     while i<n:
...         print("我先在\"yield "+str(i)+"\"前睡了，等__next__來再叫我")
...         yield i
...         i+=1
... 
>>> for i in my_range(5):
...     print(i)
... 
我先在"yield 0"前睡了，等__next__來再叫我
0
我先在"yield 1"前睡了，等__next__來再叫我
1
我先在"yield 2"前睡了，等__next__來再叫我
2
我先在"yield 3"前睡了，等__next__來再叫我
3
我先在"yield 4"前睡了，等__next__來再叫我
4
>>> 

範例中的my_range()就是一個generator，可以說generator就是內部含有yield語句的function，而因為呼叫__next__所需要的回傳值就直接從yield語句來產生出來，所以一個yield語句就省得我們自己多花功夫定義一個__next__方法，使得程式碼更為精簡，這是上面提及的第一個優點。

範例中我試著用generator實作簡單的range()功能，我在這裡先說明一下generator的一個特性，就是"lazy evaluation"，generator function不會一呼叫就會全部跑完，他跑到了yield語句就會停下來休息，等到__next__跑來催他，他才會不甘不願的爬起來，吐出yield後面的值作為__next__的回傳值後繼續開工，再遇到了yield就再停下來休息....如此的不停反覆，所以我在範例中加上"print("我先在"yield "+str(i)+""前睡了，等__next__來再叫我")"這句，並不會在呼叫my_range(5)後馬上print出連續五行出來，而是遇到yield就休息，等到for迴圈用呼叫__next__再繼續工作，從輸出的結果可以證明這件事情。

在版本差異系列五有提到過python3的range()和python2的range()的差異，python2的range是直接產出一個list，其使用的記憶體單位數和list的長度成正比，若是range()裏面的參數過大，不管是記憶體空間還是程式執行效能，都會是很大的負擔，但python3的range就是generator的結構，所以如同範例一樣，用"lazy evaluation"的方式產出回傳值，每一次只花費了一單位的記憶體用於儲存回傳值，而這也導致了generator對記憶體的使用非常節省，也就是我說的generator的第二個優點。

事實上generator可不只有yield這個權柄可以用，他還有另一個好用的武器，就是'yield from'，原本的yield是用來產生一個值作為__next__的回傳，而yield from是把迭代的工作交給另外一個iterator，這也使遞迴式的迭代行為變得容易實作，也就是上面所說的第三個優點，比如說我們想要建構一個內部結構如下圖的二元樹：

然後實作出post-order,in-order,pre-order等三個迭代行為，'yield from'使我們的工作減輕許多：

class Node:
    def __init__(self,value):
        self.root = value
        self.left = None
        self.right = None

    def add_leftChild(self,node):
        if type(node) != type(Node(0)):
            raise TypeError
        else:
            self.left = node
        
    def add_rightChild(self,node):
        if type(node) != type(Node(0)):
            raise TypeError
        else:
            self.right = node

    def __repr__(self):
        return 'Node({!r}).format(self.root)'

    def post_order(self):
        yield self.root
        if self.left!=None:
            yield from self.left.post_order()
        if self.right!=None:
            yield from self.right.post_order()

    def in_order(self):
        if self.left!=None:
            yield from self.left.in_order()
        yield self.root 
        if self.right!=None:
            yield from self.right.in_order()

    def pre_order(self):
        if self.left!=None:
            yield from self.left.pre_order()
        if self.right!=None:
            yield from self.right.pre_order()
        yield self.root

root = Node(8)
node3 = Node(3)
node1 = Node(1)
node4 = Node(4)
node6 = Node(6)
node7 = Node(7)
node10 = Node(10)
node14 = Node(14)
node13 = Node(13)
root.add_leftChild(node3)
node3.add_leftChild(node1)
node3.add_rightChild(node6)
node6.add_leftChild(node4)
node6.add_rightChild(node7)
root.add_rightChild(node10)
node10.add_rightChild(node14)
node14.add_leftChild(node13)

for node in root.post_order():
    print(node,end=' ')
print('')
for node in root.in_order():
    print(node,end=' ')
print('')
for node in root.pre_order():
    print(node,end=' ')
print('')

在範例中，每一種迭代行為利用遞迴方式去實作，用簡短的5行程式碼就能實現，這都歸功於'yield form'的大能，而且完全不會因為要滿足迭代需求而去動到其他的內部方法，也就是說post_order(self),in_order(self),pre_order(self)可以與Node的其他方法完全隔離開來，如果要自己用實作__next__方法來實現這些功能，可能還要去紀錄當下訪問的節點是最初的root或是還有父節點存在，另外可能還必須自己在__next__觸發StopIteration，這些額外的工作都非常勞心傷神，而且維護也不容易，實在是個不妥的方法。